This invention relates to a system for compressing or compacting halftone, line and text data where resolution and halftone screen frequency may be unknown, and more particularly to a circuit and method for adaptive predicting which uses a plurality of predictor patterns but which does not require transmission of additional code to the receiver to identify the particular pattern used.
In systems that digitally reproduce documents or other pictorial information, it is generally desirable to compress the data to reduce the requirements on system bandwidth and storage. Compression is achieved by encoding long runs of zeros or ones. Larger runs of zeros can be achieved by predicting each bit and denoting correct prediction by a zero and an error by a one. The need for prediction is greatest for halftoned data which is almost exclusively very short runs of zeros and ones.
It is desirable that an image reproducing system compress images well regardless of their composition. Since prediction is based on the correlation between neighboring data bits, a problem arises from the fact that the correlation between bits in documents containing halftone pictures is fundamentally different from that in documents containing text and line drawings. Predictors that work well for one do not work well for the other. Furthermore, the correlation in documents containing halftones is highly dependent upon the scanning resolution and the screen frequency of the halftones. Given a document composed of text, a halftone picture from a magazine, and a halftone picture from a newspaper, no single predictor would perform well on all regions of the document.
To accommodate such a mixture of data, multiple predictor arrangements have been employed in the past. These schemes typically utilize selector logic to choose from among a group of predictors that predictor which best predicts the present data block. The main disadvantage of such schemes is the necessity to include predictor change codes as part of the final output so that the receiver's decompressor will know which predictor pattern to use in the deprediction process. The addition of these codes result in poorer compression. A trade-off must be made by choosing a larger data block size over which a predictor is applicable. This leads to a second disadvantage, the error codes for each predictor must be buffered for the entire block pending the outcome of the selection process.
It will become apparent that the drawbacks accompanying past multiple predictor arrangements have been overcome by the improved predictor algorithm employed by the circuit herein described.
The present invention is defined by a set of simple predictors and an algorithm for selecting the appropriate predictor for each current data block.
It is an object of the present invention to provide an improved system for adaptively predicting documents containing halftone, text, and line copy data.
It is an object of the present invention to provide an adaptive prediction process that does not require any knowledge of the composition of the document to be predicted.
It is an object of the present invention to provide method and apparatus for predicting halftone data whose screen frequency and resolution are unknown.
It is an object of the present invention to provide an adaptive prediction process that does not require the transmission of additional codes.
It is an object of the present invention to provide an adaptive prediction process that does not require buffering large amounts of predictor output while predictor selection is pending.
It is an object of the present invention to provide an adaptive prediction process that is able to adapt quickly to changing correlations.
The fundamental idea behind the current invention is that both the predictor and the depredictor select the predictor (depredictor) for the current data block based on which predictor would have performed best (least errors) on the previous data block. If a particular predictor would have worked well on the previous data block, it is likely that it will work well on the next data block. Since the data necessary for making the decision is available to both transmitter and receiver, no extra data need be transmitted.
The general rule is that the predictor that performed best on the previous block will be used for the current block, and that in case of ties, the predictor used previously (or the predictor in the class that was used previously) will be used. There is an exception, and that is for halftones, where the pitch inevitably remains fixed for the duration of the image. To take advantage of this, a new halftone predictor will not be selected unless it performs better than the previously selected one for two consecutive blocks.